#!/usr/bin/python
# -*- coding: utf-8 -*-

"""
Module implementing cMainWindow.
"""

from PyQt4.QtCore import pyqtSlot
from PyQt4 import QtGui, QtCore
from PyQt4.QtGui import QMainWindow
import os

from Ui_main_window import Ui_MainWindow
from cLocation import cLocation
from thread import cWideSearch, cHistory

class cMainWindow(QMainWindow, Ui_MainWindow):

    Nothing = 0
    Wall = 8
    Box  = 4
    Target = 2
    Person = 1
    
    StatusList = [Nothing, Wall, Box, Target, Person, \
                  Target+Box, Target+Person]
    StatusNext = {Nothing:Wall, Wall:Box, Box:Target, Target:Person, \
                  Person:Target+Box, Target+Box:Target+Person, \
                  Target+Person:Nothing}
    StatusLast = {Wall:Nothing, Box:Wall, Target:Box, Person:Target, \
                  Target+Box:Person, Target+Person:Target+Box, \
                  Nothing:Target+Person}

    def FindDynamicDeadPoint(self, stat):
        # One passage can not contain two boxes
        for aPassage in self.Passages:
            BoxNumber = 0
            for loc in aPassage:
                if stat[loc.x][loc.y] & self.Box:
                    BoxNumber += 1
            if BoxNumber >= 2:
                return True
        return False
    
    def FindDeadPoints(self):
        self.Dead = []
        for i in range(self.Rows):
            tmp = []
            for j in range(self.Columns):
                tmp.append(0)
            self.Dead.append(tmp)
        # Corner points
        for i in range(self.Rows):
            for j in range(self.Columns):
                if self.Status[i][j] == self.Wall or \
                   self.Status[i][j] & self.Target:
                    continue
                xCount, yCount = 0, 0
                Loc = cLocation(i, j)
                for moved in [cLocation(0, 1), cLocation(0, -1)]:
                    newLoc = Loc.Move(moved)
                    if newLoc.IfOut(self.Rows, self.Columns):
                        xCount = 1
                        break
                    if self.Status[newLoc.x][newLoc.y] == self.Wall:
                        xCount = 1
                        break
                for moved in [cLocation(1, 0), cLocation(-1, 0)]:
                    newLoc = Loc.Move(moved)
                    if newLoc.IfOut(self.Rows, self.Columns):
                        yCount = 1
                        break
                    if self.Status[newLoc.x][newLoc.y] == self.Wall:
                        yCount = 1
                        break
                if xCount > 0 and yCount > 0:
                    self.Dead[i][j] = 1
        # A horizontal line with up/down walls, without Targets
        for i in range(self.Rows):
            lines = []
            tmp = []
            for j in range(self.Columns):
                if self.Status[i][j] & self.Wall and len(tmp)>0:
                    lines.append(tmp)
                    tmp = []
                else:
                    tmp.append(cLocation(i, j))
            if len(tmp) > 0:
                lines.append(tmp)
            for oneline in lines:
                # see if there are Targets
                ifContinue = False
                for aLoc in oneline:
                    if self.Status[aLoc.x][aLoc.y] & self.Target:
                        ifContinue = True
                        break
                if ifContinue:
                    continue
                # see if it is the top or bottom then mark
                if oneline[0].x == 0 or oneline[0].x == self.Rows-1:
                    for aLoc in oneline:
                        self.Dead[aLoc.x][aLoc.y] = 1
                    continue
                # see if ALL upward/downward grids are walls then mark
                ifContinue = True
                for aLoc in oneline:
                    if (not self.Status[aLoc.x-1][aLoc.y] & self.Wall) and \
                       (not self.Status[aLoc.x+1][aLoc.y] & self.Wall):
                        ifContinue = False
                        break
                if ifContinue:
                    for aLoc in oneline:
                        self.Dead[aLoc.x][aLoc.y] = 1
                    continue
        # A vertical line with left/right walls, without Targets
        for j in range(self.Columns):
            lines = []
            tmp = []
            for i in range(self.Rows):
                if self.Status[i][j] & self.Wall and len(tmp)>0:
                    lines.append(tmp)
                    tmp = []
                else:
                    tmp.append(cLocation(i, j))
            if len(tmp) > 0:
                lines.append(tmp)
            for oneline in lines:
                # see if there are Targets
                ifContinue = False
                for aLoc in oneline:
                    if self.Status[aLoc.x][aLoc.y] & self.Target:
                        ifContinue = True
                        break
                if ifContinue:
                    continue
                # see if it is the top or bottom then mark
                if oneline[0].y == 0 or oneline[0].y == self.Columns-1:
                    for aLoc in oneline:
                        self.Dead[aLoc.x][aLoc.y] = 1
                    continue
                # see if ALL left/right grids are walls then mark
                ifContinue = True
                for aLoc in oneline:
                    if (not self.Status[aLoc.x][aLoc.y-1] & self.Wall) and \
                       (not self.Status[aLoc.x][aLoc.y+1] & self.Wall):
                        ifContinue = False
                        break
                if ifContinue:
                    for aLoc in oneline:
                        self.Dead[aLoc.x][aLoc.y] = 1
                    continue
                    
        # Mark the passages and chambers
        self.Passages = []
        # TODO: chambers are not concluded
        tmp_li = []
        for i in range(self.Rows):
            tmp = []
            for j in range(self.Columns):
                # 1st number: degree of connection
                # 2nd number: status (1 == passage, 2 == chamber)
                tmp.append([0, 0]) 
            tmp_li.append(tmp)
        # calculate the degree of connection
        for i in range(self.Rows):
            for j in range(self.Columns):
                if self.Status[i][j] == self.Wall:
                    continue
                if self.Status[i][j] & self.Target: # enlarge the connecty of Target cell
                    tmp_li[i][j][0] += 3
                nowLoc = cLocation(i, j)
                for moved in [cLocation(0, 1), cLocation(0, -1), \
                      cLocation(1, 0), cLocation(-1, 0)]:
                    newLoc = nowLoc.Move(moved)
                    if newLoc.IfOut(self.Rows, self.Columns):
                        continue
                    if self.Status[newLoc.x][newLoc.y] != self.Wall:
                        tmp_li[i][j][0] += 1
                # judge the passage and the chambers
                if tmp_li[i][j][0] == 2:
                    tmp_li[i][j][1] = 1 # passage
                elif tmp_li[i][j][0] > 2:
                    tmp_li[i][j][1] = 2 # chambers
        # Store the passages into the lists
        while self.WideSearch_Passages(tmp_li):
            pass
                 
    def WideSearch_Passages(self, tmp_li):
        # Find the first elem of passage
        ifFound = False
        for i in range(self.Rows):
            for j in range(self.Columns):
                if (not ifFound) and tmp_li[i][j][1] == 1: # passage
                    self.Passages.append([cLocation(i, j)])
                    tmp_li[i][j][1] = -1 # used
                    ifFound = True
        if not ifFound:
            return False # terminate the wide search
        # Wide search
        NowNum = 0
        while NowNum < len(self.Passages[-1]):
            nowLoc = self.Passages[-1][NowNum]
            for moved in [cLocation(0, 1), cLocation(0, -1), \
                      cLocation(1, 0), cLocation(-1, 0)]:
                newLoc = nowLoc.Move(moved)
                if newLoc.IfOut(self.Rows, self.Columns):
                    continue
                if newLoc.IsIn(self.Passages[-1]):
                    continue
                if tmp_li[newLoc.x][newLoc.y][1] == 1: # passage
                    tmp_li[newLoc.x][newLoc.y][1] = -1
                    self.Passages[-1].append(newLoc)
            NowNum += 1
        return True # continue the wide search
        
    def Diffusion(self, stat, res, Diffusive, NowDiffIndex):
        # a wide search for person diffusivity
        for moved in [cLocation(0, 1), cLocation(0, -1), \
                      cLocation(1, 0), cLocation(-1, 0)]:
            nowLoc = Diffusive[NowDiffIndex].Move(moved)
            if nowLoc.IfOut(self.Rows, self.Columns):
                continue
            if (not stat[nowLoc.x][nowLoc.y] & self.Wall) and \
               (not stat[nowLoc.x][nowLoc.y] & self.Box) and \
               (not nowLoc.IsIn(Diffusive)):
                # add to history
                Diffusive.append(nowLoc)
                res[nowLoc.x][nowLoc.y] = 1

    def CheckConnecty(self, stat):
        # find the places that the person can go
        res = []
        Diffusive = []
        for i in range(self.Rows):
            tmp = []
            for j in range(self.Columns):
                if stat[i][j] & self.Person:
                    tmp.append(1)
                    Diffusive.append(cLocation(i, j))
                    NowDiffIndex = 0
                else:
                    tmp.append(0)
            res.append(tmp)
        while NowDiffIndex < len(Diffusive):
            self.Diffusion(stat, res, Diffusive, NowDiffIndex)
            NowDiffIndex += 1
        return res
        
    def FindSimilarity_less(self, stat):
        # define the similarity between current status and goal
        # only valide when the number of boxes is small
        # find the Boxes and Targets
        perm = lambda x: [] if not x else [x] if len(x) == 1 \
               else [list(x[i:i+1])+y for i in range(len(x)) \
               for y in perm(list(x[:i])+list(x[i+1:]))]
        Boxes, Targets = [], []
        for i in range(self.Rows):
            for j in range(self.Columns):
                if stat[i][j] & self.Box:
                    Boxes.append(cLocation(i, j))
                if stat[i][j] & self.Target:
                    Targets.append(cLocation(i, j))
        minDis = 100000
        for indexes in perm(range(len(Targets))):
            Dis = 0
            for i in range(len(Targets)):
                Dis += Boxes[i].Distance(Targets[indexes[i]])
            if Dis < minDis:
                minDis = Dis
        return minDis
    
    def FindSimilarity(self, stat):
        # define the similarity between current status and goal
        # not exact solution
        # find the Boxes and Targets
        Boxes, Targets = [], []
        for i in range(self.Rows):
            for j in range(self.Columns):
                if stat[i][j] & self.Box:
                    Boxes.append(cLocation(i, j))
                if stat[i][j] & self.Target:
                    Targets.append(cLocation(i, j))
        res = 0
        for Box in Boxes:
            # find the shortest way to Target
            minDis = 100000
            minLoc = 0
            for tInd in range(len(Targets)):
                Target = Targets[tInd]
                Dis = Box.Distance(Target)
                if Dis < minDis:
                    minDis = Dis
                    minLoc = tInd
            res += minDis
            minDis = Targets.pop(minLoc)
        return res
    
    def List2Str(self, stat):
        res = ""
        for i in range(self.Rows):
            for j in range(self.Columns):
                res += str(stat[i][j])
        res += str(self.FindSimilarity(stat))
        return res
    
    def Str2List(self, strs):
        res = []
        for i in range(self.Rows):
            tmp = []
            for j in range(self.Columns):
                tmp.append(int(strs[i*self.Columns+j]))
            res.append(tmp)
        return res
    
    def UpdateAll(self, showPassage=False):
        if showPassage:
            texts = []
            for i in range(self.Rows):
                tmp = []
                for j in range(self.Columns):
                    tmp.append("")
                texts.append(tmp)
            PassageNum = 1
            for onePassage in self.Passages:
                for loc in onePassage:
                    texts[loc.x][loc.y] = str(PassageNum)
                PassageNum += 1
        for i in range(self.Rows):
            for j in range(self.Columns):
                if showPassage:
                    self.UpdateCell(i, j, showPassage, texts)
                else:
                    self.UpdateCell(i, j, showPassage);
        
    def UpdateCell(self, row, column, showPassage=False, texts=[]):
        stat = self.Status[row][column]
        newItem = QtGui.QTableWidgetItem()
        if stat&self.Wall:
            newItem.setBackgroundColor(QtCore.Qt.black)
        elif stat&self.Target:
            newItem.setBackgroundColor(QtCore.Qt.yellow)
        elif self.chkDead.isChecked() and self.Dead[row][column] == 1:
            newItem.setBackgroundColor(QtCore.Qt.cyan)
        else:
            newItem.setBackgroundColor(QtCore.Qt.white)
        if not showPassage:
            if stat&self.Box:
                newItem.setText("B")
            elif stat&self.Person:
                newItem.setText("P")
            else:
                newItem.setText("")
        else: # showPassage
            newItem.setText(texts[row][column])
        newItem.setTextAlignment(4)
        self.tableWidget.setItem(row, column, newItem)        
                
    
    def __init__(self, parent = None):
        """
        Constructor
        
        @param parent reference to the parent widget (QWidget)
        """
        QMainWindow.__init__(self, parent)
        self.setupUi(self)
        self.tableWidget.setEnabled(False)
        self.thread = cWideSearch()
        self.thread.Father = self
        self.connect(self.thread, QtCore.SIGNAL("updateTime()"), \
                     self.updateTime)
        self.connect(self.thread, QtCore.SIGNAL("mbox()"), \
                     self.mbox)
        self.progressBar.setValue(0)
    
    @pyqtSlot()
    def on_btnChangeSize_clicked(self):
        # Change the size of the listview
        self.Rows = self.spin_Row.value()
        self.Columns = self.spin_Column.value()
        self.RowColumn = self.Rows*self.Columns
        
        self.tableWidget.setEnabled(True)
        self.tableWidget.setRowCount(self.spin_Row.value())
        self.tableWidget.setColumnCount(self.spin_Column.value())
        self.Status = []
        for i in range(self.spin_Row.value()):
            tmp = []
            for j in range(self.spin_Column.value()):
                tmp.append(self.Nothing)
            self.Status.append(tmp)
        self.FindDeadPoints()
        self.UpdateAll()

    @pyqtSlot(int, int)
    def on_tableWidget_cellClicked(self, row, column):
        if self.tableWidget.button == QtCore.Qt.LeftButton:
            self.Status[row][column] = self.StatusNext[self.Status[row][column]]
        else:
            self.Status[row][column] = self.StatusLast[self.Status[row][column]]
        self.FindDeadPoints()
        self.UpdateAll()

    @pyqtSlot()
    def on_btnSolve_clicked(self):
        self.thread.stop()
        self.HistoryArray = []
        self.Now = 0
        statusStr = self.List2Str(self.Status)
        self.HistoryArray.append(cHistory(statusStr, -1, cLocation(0, 0)))
        self.Found = False
        if not self.Found:
            self.thread.start()

    @pyqtSlot()
    def on_btnStop_clicked(self):
        self.thread.stop()

    @pyqtSlot()
    def on_btnContinue_clicked(self):
        self.thread.start()

    def updateTime(self):
        self.lblStatus.setText("Nodes:"+str(len(self.HistoryArray)) \
            + os.linesep + "NowNode:"+str(self.Now))
        self.progressBar.setValue(int(self.Now*100/len(self.HistoryArray)))

    def mbox(self):
        mbox = QtGui.QMessageBox()
        if self.Found:
            mbox.setText("Found solution.")
        else:
            mbox.setText("No solution.")
        mbox.exec_()

    def DiffSearch(self, DiffHis, DiffLoc, stat2_str):
        def IsIn(statstr, strList):
            for elem in strList:
                if statstr == elem[0]:
                    return True
            return False
        
        #print(DiffHis, stat2_str)
        # if meets
        if DiffHis[DiffLoc][0] == stat2_str:
            return True
        stat = self.Str2List(DiffHis[DiffLoc][0])
        for i in range(self.Rows):
            for j in range(self.Columns):
                if stat[i][j] & self.Person:
                    LocPerson = cLocation(i, j)
        for moved in [cLocation(0, 1), cLocation(0, -1), \
                      cLocation(1, 0), cLocation(-1, 0)]:
            newLoc = LocPerson.Move(moved)
            if newLoc.IfOut(self.Rows, self.Columns):
                continue
            if (not stat[newLoc.x][newLoc.y] & self.Wall) and \
               (not stat[newLoc.x][newLoc.y] & self.Box):
                # copy a new stat
                newstat = []
                for i in range(self.Rows):
                    tmp = []
                    for j in range(self.Columns):
                        tmp.append(stat[i][j])
                    newstat.append(tmp)
                newstat[LocPerson.x][LocPerson.y] -= self.Person
                newstat[newLoc.x][newLoc.y] += self.Person
                newstatstr = self.List2Str(newstat)
                if IsIn(newstatstr, DiffHis):
                    continue
                # add to history
                DiffHis.append((newstatstr, DiffLoc))
        return False

    def ExtractNodes(self):
        self.HistoryView = []
        for i in range(len(self.HistoryNodes)-1):
            # get the stage just before the final distination
            stat2 = self.Str2List(self.HistoryNodes[i+1].statstr)
            for ii in range(self.Rows):
                for j in range(self.Columns):
                    if stat2[ii][j] & self.Person:
                        LocPerson = cLocation(ii, j)
            LocPush = LocPerson.Move(self.HistoryNodes[i+1].loc)
            LocBox  = LocPerson.MoveInv(self.HistoryNodes[i+1].loc)
            stat2[LocPerson.x][LocPerson.y] -= self.Person
            stat2[LocPush.x][LocPush.y] += self.Person
            stat2[LocPerson.x][LocPerson.y] += self.Box
            stat2[LocBox.x][LocBox.y] -= self.Box
            stat2_str = self.List2Str(stat2)
            #print(self.HistoryNodes[i+1].statstr, stat2_str)
            # add the path between stat1 and stat2 (both included)
            # new wide search
            DiffHis = [(self.HistoryNodes[i].statstr, -1)]
            DiffLoc = 0
            while (1):
                if self.DiffSearch(DiffHis, DiffLoc, stat2_str):
                    break
                DiffLoc += 1
            # review the parents until root
            LocView = len(self.HistoryView)
            while DiffLoc != -1:
                self.HistoryView.insert(LocView, DiffHis[DiffLoc][0])
                DiffLoc = DiffHis[DiffLoc][1]
        self.HistoryView.append(self.HistoryNodes[-1].statstr)
    
    @pyqtSlot()
    def on_chkDead_clicked(self):
        self.UpdateAll()
        
    @pyqtSlot()
    def on_btnInitReview_clicked(self):
        # reconstruct the path
        Nowloc = self.Now - 1 
        self.HistoryNodes = []
        while Nowloc != -1:
            self.HistoryNodes.insert(0, self.HistoryArray[Nowloc])
            Nowloc = self.HistoryArray[Nowloc].parent
        
        # from HistoryNodes to HistoryView
        self.ExtractNodes()
        
        # display
        self.spin_Review.setMinimum(1)
        self.spin_Review.setMaximum(len(self.HistoryView))
        self.spin_Review.setValue(1)
        self.on_spin_Review_valueChanged(1)
    
    @pyqtSlot(int)
    def on_spin_Review_valueChanged(self, p0):
        self.Status = self.Str2List(self.HistoryView[p0-1])
        self.UpdateAll()

    @pyqtSlot()
    def on_chkPassage_pressed(self):
        # Show passages
        self.UpdateAll(True)
    
    @pyqtSlot()
    def on_chkPassage_released(self):
        self.chkPassage.setCheckState(False)
        self.UpdateAll()


if __name__ == "__main__":
    import sys
    app = QtGui.QApplication(sys.argv)
    ui = cMainWindow()
    ui.show()
    sys.exit(app.exec_())
